package com.brett.frame.learn.tree;

import com.brett.frame.learn.util.TreeBuilder;
import com.brett.frame.learn.util.TreeBuilder.TreeNode;

/**
 * 二叉搜索树
 * 如果左节点不为null，那左树上所有节点值都小于其父节点值，
 * 如果右节点不为null,那右树上所有节点值都大于其父节点值。
 * @author lenovo
 *
 */
public class BinarySearchTree implements Tree {
	private TreeNode root;

	@Override
	public boolean insert(int data) {
		if (root == null) {
			root = new TreeNode(data);
			return true;
		} else {
			TreeNode cur = root;
			while (cur != null) {
				if (cur.getData() >= data) {
					if (cur.getLeftNode() == null) {
						cur.setLeftNode(new TreeNode(data));
						return true;
					}
					cur=cur.getLeftNode();
				} else {
					if(cur.getRightNode()==null) {
						cur.setRightNode(new TreeNode(data));
						return true;
					}
					cur=cur.getRightNode();
				}
			}
		}
		return false;
	}

}
